
# ================ CONFIG

OUTPUT_FILE = "./in.txt"

# ================
import random



def randInt(l = 1, r = 1000000000):
    if (l > r):
        raise Exception("l > r", l, r)
    return random.randint(l, r);

def randPair(l, r, ordered = False):
    a = randInt(l, r)
    b = randInt(l, r)
    while a == b:
        a = randInt(l, r)
        b = randInt(l, r)
    if a > b and ordered:
        k = a
        a = b
        b = k
    return (a, b)

def randArr(l, r, n):
    res = []
    for i in n:
        res.append(randInt(l, r))

def genNonIntersectIntervals(n, m = 500, k = 10):
    dat = []
    while n > 0:
        x = randInt(1, min(n, m))
        if n < k:
            x = n
        n = n - x
        dat.append(x)
    p = 0
    res = []
    for x in dat:
        for i in range(1, x+1):
            res.append([p+i, p+2*x+1-i])
        p = p + 2*x
    return res

def genGraph(n, m, isDirected = False, isWeighed = 0):
    if m < n-1:
        raise Exception("m < n-1", n, m)
    fa = [0 for i in range(n+1)]
    fa[1] = 0

    S = set()
    for i in range(2, n+1):
        fa[i] = randInt(1, i-1)
        S.add((fa[i], i))

    for i in range(n-1, m):
        p = randPair(1, n, not isDirected)
        while S.__contains__(p):
            p = randPair(1, n, not isDirected)
        S.add(p)

    s = "{} {}\n".format(n, m)
    e = [s]
    for p in S:
        cs = "{} {}".format(p[0], p[1])
        if isWeighed > 0:
            cs = cs + " {}\n".format(randInt(0, isWeighed))
        else:
            cs = cs + "\n"
        e.append(cs)
    s = "".join(e)
    # f.write(s)
    return s

def randArray(n, l, r):
    a = [0 for i in range(n)]
    for i in range(n):
        a[i] = randInt(l, r)
    return a
    
def randPermutation(n, base=1):
    a = [0 for i in range(n)]
    x = randInt(1, 3 * n + 7)
    for i in range(n):
        a[i] = i + base
    for i in range(x):
        p = randPair(0, n-1)
        k = a[p[0]]
        a[p[0]] = a[p[1]]
        a[p[1]] = k
    return a

def printArray(a):
    n = a.__len__()
    for i in range(n):
        print(a[i], end="")
        if (i == n-1):
            print()
        else:
            print(' ', end="")



def randTree(n, u=[], v=[]):
    f = [0 for i in range(n + 1)]
    for i in range(2, n + 1):
        f[i] = randInt(1, i - 1)
    for i in range(n - 1):
        u[i], v[i] = f[i + 2], i + 2
        
# genGraph(5, 7, False, 10)
